
// 44 .通配符匹配
class Solution {
public:
    bool isMatch(string s, string p) {
        // 使用动态规划来实现
        s = " " + s , p = " " + p;
        int n1 = s.size() , n2 = p.size();
        vector<vector<bool>> dp(n1, vector<bool>(n2));
        for(int i = 1 ; i < n1 ; i++)                       // p是空串
            dp[i][0] = false;
        dp[0][0] = true;
        for(int i = 1 ; i < n2 ; i++)                       // s是空串
        {
            if(p[i] == '*')  dp[0][i] = dp[0][i - 1];
            else   dp[0][i] = false;
        }
        // 考试动态规划 
        for(int i = 1 ; i < n1 ;i++)
        {
            for(int j = 1 ; j < n2 ;j++)
            { 
                if(p[j] == '?')  dp[i][j] = dp[i - 1][j - 1];
                else if(p[j] == '*') dp[i][j] = dp[i][j - 1]||dp[i - 1][j];
                else if(s[i] == p[j]) dp[i][j] = dp[i - 1][j - 1];
            }
        }
        return dp[n1-1][n2-1];
    }
};